Convex relaxation for finding planted influential nodes in a social network

摘要

We consider the problem of maximizing influence in a social network. We focuson the case that the social network is a directed bipartite graph whose arcsjoin senders to receivers. We consider both the case of deterministic networksand probabilistic graphical models, that is, the so-called "cascade" model. Theproblem is to find the set of the $k$ most influential senders for a giveninteger $k$. Although this problem is NP-hard, there is a polynomial-timeapproximation algorithm due to Kempe, Kleinberg and Tardos. In this work weconsider convex relaxation for the problem. We prove that convex optimizationcan recover the exact optimizer in the case that the network is constructedaccording to a generative model in which influential nodes are planted but thenobscured with noise. We also demonstrate computationally that the convexrelaxation can succeed on a more realistic generative model called the "forestfire" model.